Sau khi cùng đội tuyển U-17 Nhật Bản tại Giải vô địch bóng đá U-17 thế giới 1993 (ghi một bàn) và cùng U-20 Nhật Bản dự Giải vô địch bóng đá U-20 thế giới 1995 (ghi hai bàn), Nakata được triệu tập vào đội hình U-23 Nhật Bản tham dự Thế vận hội 1996, nơi Nhật Bản bất ngờ vượt qua U-23 Brasil,[16] và Thế vận hội 2000. Anh ra mắt Đội tuyển bóng đá quốc gia Nhật Bản vào tháng 5 năm 1997 trong trận gặp Hàn Quốc.[17]

Anh là cầu thủ chủ chốt giúp Nhật Bản giành vé dự Giải vô địch bóng đá thế giới 1998 với năm bàn thắng tại vòng loại và kiến tạo cả ba bàn thắng của Nhật Bản trong trận play-off với Iran. Anh giúp Nhật Bản lọt vào chung kết Cúp Liên đoàn các châu lục 2001 nhưng không tham dự trận chung kết vì phải thi đấu trận đấu cuối cùng của mùa giải cho Roma.[18] Nakata thi đấu cả bốn trận của Nhật Bản tại Giải vô địch bóng đá thế giới 2002 trên sân nhà, ghi bàn trong chiến thắng 2–0 ở vòng bảng trước Tunisia.

Tại Giải vô địch bóng đá thế giới 2006, Nakata thi đấu cả ba trận của Nhật Bản, thua Úc và Brasil, hòa Croatia. Anh là Cầu thủ xuất sắc nhật trận đấu trong trận gặp Croatia.[19] Sau World Cup 2006 Nakata tuyên bố giã từ sự nghiệp bóng đá đỉnh cao.[20][21] Trong cuộc phỏng vấn vào năm 2014 với tạp chí TMW, Nakata giải thích rằng anh giải nghệ khi còn rất trẻ như vậy là do anh không còn cảm hứng chơi bóng, và muốn khám phá thế giới xung quanh.[22]

Mặc dù Nakata có mặt ở mọi trận đấu trong ba kỳ World Cup đầu tiên của Nhật Bản, tuy nhiên anh không có tên trong các đội hình vô địch Cúp bóng đá châu Á vào các năm 2000 và 2004. Anh có tổng cộng 77 lần ra sân cho đội tuyển quốc gia, ghi 11 bàn, trong đó có 9 bàn ở các giải đấu của FIFA.[17]